package jzOffer;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class MaxQueue {
    Queue<Integer> q1;
    Deque<Integer> q2;
    public MaxQueue() {
        q1=new LinkedList<>();//存数据
        q2=new LinkedList<>();//辅助的
    }

    public int max_value() {
        return q2.isEmpty()?-1:q2.peekFirst();
    }

    public void push_back(int value) {
        q1.offer(value);
        while(!q2.isEmpty() && value>q2.peekLast()){
            q2.pollLast();
        }
        q2.offerLast(value);
    }

    public int pop_front() {
        while (q1.isEmpty()) return -1;
        if(q1.peek().equals(q2.peekFirst())){
            q2.pollFirst();
        }
        return q1.poll();
    }

}

public class Num59of2 {

}
